package com.cn.codebrush.数组;


import java.util.ArrayList;
import java.util.List;

public class No56合并区间 {
    public static void main(String[] args) {

        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        System.out.println(merge(intervals));

    }












    

    /**
     * 想用分治法  但是是错的
     */
    static List list = new ArrayList<>();
    public static int[][] merge(int[][] intervals) {
        mergeWork(intervals,0,intervals.length-1);
        return null;
    }

    public static int[] mergeWork(int[][] intervals,int left,int right) {
        if(left == right) {
            return intervals[left];
        }else {
            int mid = (left+right)/2;
            int[] leftNums = mergeWork(intervals,left,mid);
            int[] rightNums = mergeWork(intervals,mid+1,right);
            int[] nums = mergeHelper(leftNums,rightNums);
            //list.add(nums);
            return nums;
        }
    }

    /**
     * [1,2][3,4]
     * [1,3][2,4]
     * [1,4][2,3]
     *
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] mergeHelper(int[] nums1, int[] nums2) {
        if(nums1[1] < nums2[0]){
            list.add(nums1);
            return nums2;
        }else if(nums1[1] >= nums2[0]){
            if(nums1[1] >= nums2[1]){
                list.add(nums2);
                return nums1;
            }else {
                return new int[]{nums1[0],nums2[1]};
            }
        }

        return null;
    }
}
